Circuit-switched network architectures, such as those based on synchronous optical network (SONET) or synchronous digital hierarchy (SDH) standards, were originally designed to support voice traffic using dedicated fixed-bandwidth connections. Although such networks are advantageous in that they incorporate substantial reliability and protection mechanisms, their primary disadvantage has been a lack of bandwidth efficiency.
Packet-switched network architectures, which include those based on asynchronous transfer mode (ATM) or Internet protocol (IP) standards, have traditionally been much better able than circuit-switched architectures to handle data traffic. Since data traffic is inherently bursty, it leads to underutilization of the fixed-bandwidth connections of conventional circuit-switched networks. Packet-switched network architectures provide the benefits of statistical multiplexing, which allows for better handling of bursty data traffic.
Recently, virtual concatenation (VC) and link capacity adjustment scheme (LCAS) protocols have been developed which allow more efficient use of the existing fixed-bandwidth connections associated with circuit-switched SONET/SDH network infrastructure. For example, these protocols are utilized in transmission of Ethernet over SONET (EoS) data traffic over metropolitan networks, and in numerous other data transmission applications. The VC and LCAS protocols are described in greater detail in, for example, ITU-T standards documents G.707 and G.7042, respectively, both of which are incorporated by reference herein.
Virtual concatenation generally allows a given source node of a network to form a virtually-concatenated group (VCG) which includes multiple members each associated with a corresponding data stream. The different data streams may then be transmitted over diverse routes through the network from the source node to a given destination node. The destination node recombines the streams to reconstruct the original VCG.
The LCAS protocol enhances the basic virtual concatenation functionality described above by allowing so-called “hitless” addition and deletion of members from a VCG, that is, addition and deletion of members without the introduction of errors into the transmitted data. The LCAS protocol also enables a VCG to operate at a reduced capacity after the failure of routes associated with one or more members, by allowing the temporary removal of members associated with failed routes from the VCG.
Despite the improvements associated with the recently-developed VC and LCAS protocols, there remain problems in both circuit-switched and packet-switched network architectures. Generally, existing architectures can be difficult to scale so as to accommodate large mesh topologies, and can still suffer from bandwidth efficiency or switching complexity concerns. For example, an architecture comprising an IP overlay over SONET may require an excessive amount of link bandwidth, while a pure IP network architecture will typically require a large amount of packet switching capacity at each network node.
The above-cited U.S. patent application Ser. No. 10/785,352 discloses an improved network architecture that can provide bandwidth efficiency without requiring high packet switching capacities at each node. In an illustrative embodiment of this load-balanced network architecture, there are N participating network nodes. An incoming packet flow of rate R at a given one of the nodes is split into N substantially equal parts, each having a rate of R/N. The packet flow is split into the N parts in a manner independent of the particular destination node or nodes that may be associated with that flow. The N parts of the incoming packet flow are distributed to respective ones of the N participating nodes, such that each of the N participating nodes receives a corresponding one of the N parts. Pre-provisioned circuits, each configured to support a rate of R/N, are used to distribute the parts to the various participating nodes. At least a subset of the participating nodes then route their respective parts to the one or more specified destination nodes. This illustrative embodiment thus routes individual parts of the given traffic flow over respective two-hop paths from a source node to a destination node via intermediate nodes. By avoiding the need for high packet switching capacities at each node, this load-balanced architecture facilitates the implementation of large-scale networks for EoS data traffic or other types of traffic flows.
An important issue that may arise in the context of load-balanced architectures such as that described in the above-cited U.S. patent application Ser. No. 10/785,352 relates to packet reordering. More specifically, by separating a given traffic flow into multiple parts, and routing the various parts to one or more destination nodes over different paths, the parts may arrive in an order other than that in which they were sent. This out-of-order packet arrival is attributable primarily to factors such as unequal delays in the various paths, and differences in the queuing of packets at participating nodes. Another factor which can influence this issue is the scheduling algorithm used at the intermediate node to schedule packets for transmission to a destination node.
A number of techniques are known in the art for dealing with the packet reordering issue in a two-stage network switch. However, these techniques exhibit a number of drawbacks, particularly in the load-balanced network architecture context described above. For example, an approach proposed in C. S. Chang et al., “Load balanced Birkhoff-Von Neumann Switches, Part II: Multi-Stage Buffering,” Computer Communications, Vol 25, pp. 611-622, 2002, involves scheduling of packets based on their expected departure times in an equivalent output queued IP router. However, this approach fails to account for path delay variations, and is thus not readily applicable to a geographically-distributed network. Another approach, described in I. Keslassy et al, “Maintaining Packet Order in Two-Stage Switches,” Proceedings of IEEE Infocom, New York, 2002, requires out-of-band communication that can result in a bottleneck.
It is therefore apparent that improved techniques are needed for dealing with the issue of packet reordering in load-balanced network architectures.